package LinearList.DoubleLink;

public class DoubleLinkedList {
    private  int size;
    private Node head;
    private Node tail;
    /**
     * 4.删
     */
    //删除某个值对应节点（第一次出现删除）
    public void removeValOnce(int val){
        //找到待删除节点
        for (Node node=head;node!=null;node=node.next) {
            if(node.val==val){
                unlink(node);
                break;
            }
        }
    }
    //删除链表中所有值为val的节点
    public void removeValAll(int val){
        for(Node node=head;node!=null;){
            if(node.val==val){//node是待删除节点
                Node temp=node.next;//暂存一下下一个节点的地址
                unlink(node);//删除node后node.next为null,得先把下一个结点的地址next暂存一下
                node=temp;//把下一节点的地址更新给node
            }else{
                node=node.next;
            }
        }
    }
    //删除index索引位置对应节点
    public void removeIndex(int index){
        if(rangeIndex(index)){
            Node node= node(index);
            unlink(node);
        }else{
            System.err.println("remove index illegal");
            return;
        }
    }
    public void removeFirst(){
        removeIndex(0);
    }
    public void removeLast(){
        removeIndex(size-1);
    }
    /**
     *所有删除操作都是删除具体节点，所以可以把它抽象成一个unlink(Node node)方法，删除双向链表中的节点
     * 思路：分治,先处理左边判断是否prev空，再看右边判断是否next空
     */
   public void unlink(Node node){
       Node prev=node.prev;
       Node next=node.next;
       if(prev==null){
           //头节点的删除
           head=next;
       }else{
           prev.next=next;
           node.prev=null;
       }
       if(next==null){
           //尾节点的删除
           tail=prev;
       }else{
           next.prev=prev;
           node.next=null;
       }
       size--;
   }

    /**
     * 3.改-根据索引修改索引位置元素值为newVal,返回未修改之前index位置的元素值
     * @param index
     * @param newVal
     * @return oldVal
     */
    public int set(int index,int newVal){
        if(rangeIndex(index)){
            Node node=node(index);
            int oldVal=node.val;
            node.val=newVal;
            return oldVal;
        }else{
            System.err.println("set index illegal");
            return -1;
        }
    }
    /**
     * 2.查找
     */
    //找元素是否存在
    public  boolean contains(int val){
        for (Node x=head;x!=null; x=x.next) {
            if(x.val==val){
                return true;
            }
        }
        return false;
    }
    //index位置对应元素
    public int get(int index){
        //index的合法性【也可以抽象为方法】
        if(rangeIndex(index)){
            return node(index).val;
        }else{
            System.err.println("get index illegal");
            return -1;
        }
    }
    private boolean rangeIndex(int index) {
        if(index<0||index>=size){
            return false;
        }
        return true;
    }

    /**
     * 1.插入
     * @param val
     */
    public void addFirst(int val){
        Node node=new Node(null,val,head);
        if(head==null){//y原先链表为null，插入的元素是第一个元素
            //head=node;
            tail=node;
        }else{
            //链表不为null
            head.prev=node;
            //head=node;
        }
        //优化：无论head是否为null，head=node,head的值都要更新为node
        // 所以可以把两行表达式提出来放在ifelse判断之后这里
        head=node;
        size++;
    }
    public void addLast(int val){
        Node node=new Node(tail,val,null);
        if(tail==null){
            //tail=node;
            head=node;
        }else{
            //链表不为空
            tail.next=node;
            //tail=node;
        }
        tail=node;
        size++;
    }
    public void addIndex(int index,int val){
        if(index<0||index>size){
            System.err.println("add index illegal");
            return;
        }else if(index==0){
            addFirst(val);
        }else if(index==size){
            addLast(val);
        }else{
            //在中间位置插入，找到index的前驱节点
            //找节点问题由于CURD都用，可以抽象成一个方法【内部用对外部不可见-private】
            Node prev=node(index-1);
            //前驱现在找到，开始插入连接四根线
            Node newNode=new Node(prev,val,prev.next);//这一步把newNode.prev=prev和newNode.next=prev.next都走了
            prev.next.prev=newNode;
            prev.next=newNode;
            size++;
        }
    }

    /**
     * 找到index索引对应的节点
     * @param index
     * @return index对应的节点node
     */
    private Node node(int index) {
        Node ret=null;
        //index<size/2,从头开始找
        if(index<(size>>1)){
            ret=head;
            for (int i = 0; i < index; i++) {
                ret=ret.next;
            }
        }else{//此时从后向前遍历
            ret=tail;
            for (int i = size-1; i >index ; i--) {
                ret=ret.prev;
            }
        }
        return ret;
    }
    public String toString(){
        String ret="";
        Node node=head;
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="NULL";
        return ret;
    }
}
class Node{
    //指向前驱节点
    Node prev;
    //保存具体值
    int val;
    //指向后继节点
    Node next;
    public Node(int val){
        this.val=val;
    }
    public Node(Node prev,int val,Node next){
        this.prev=prev;
        this.val=val;
        this.next=next;
    }
}
